import java.util.Deque;
import java.util.LinkedList;

public class Trap {
    /**
     * 方法一：单调栈解决
     * 从栈顶到栈底的元素是递增的，当前元素小于栈顶元素，则直接入栈
     * 当前元素大于栈顶元素，那么栈顶元素的前一个元素、栈顶元素和当前元素就会形成水坑，形成的水坑计算完成之后、
     * 看当前元素是都还会和战中的其他元素形成水坑
     * @param height
     * @return
     */
    public int trap(int[] height) {
        // 单调栈，从栈顶到栈底是递增的顺序
        // 当遇到比栈顶元素小的元素，就直接入栈
        // 如果遇到比栈顶元素大的元素，那么 比栈顶元素高一点的水柱、栈顶元素、当前元素的水坑
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (deque.isEmpty() || height[i] <= height[deque.peekLast()]) {
                deque.addLast(i);
            } else {
                while (deque.size() > 0 && height[i] > height[deque.peekLast()]) {
                    int mid = deque.pollLast();
                    if (deque.size() == 0) {
                        break;
                    }
                    int left = deque.peekLast();
                    sum += (Math.min(height[left], height[i])-height[mid])*(i-left-1);
                }
                deque.addLast(i);
            }
        }
        return sum;
    }

    /**
     * 前缀和，先遍历两遍数组，分别找出当前元素左边最高的水柱和右边最高的水柱
     * leftMax和rightMax数组填充完成之后，就可以遍历元素求水坑了
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        // 前缀和，先遍历两遍数组，分别记录第i个元素左边最高的水柱和右边最高的水柱
        int len = height.length;
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int max = 0;
        for (int i = 0; i < len; i++) {
            leftMax[i] = max;
            max = Math.max(max, height[i]);
        }
        max = 0;
        for (int i = len-1; i >= 0; i--) {
            rightMax[i] = max;
            max = Math.max(max, height[i]);
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += Math.max(Math.min(leftMax[i], rightMax[i])-height[i], 0);
        }
        return sum;
    }

    public static void main(String[] args) {
        Trap trap = new Trap();
        int[] arr = {4,2,0,3,2,5};
        System.out.println(trap.trap(arr));
    }
}
